Count of Subset Sum

Statement#

Given a set of positive numbers nums and a value target_sum, count the total number of subsets of the given set whose sum is equal to the target_sum.

Let’s say you are given a set = $\{$ $1, 2, 3, 4$ $\}$ and a target sum = $4$. The output will be 2 as the following subsets:

• $\{$ $1, 3$ $\}$
• $\{$ 4 $\}$

will add up to make the desired sum.

Constraints:

• $1\leq$ nums.length $\leq 1000$
• $0\leq$ target_sum $\leq 10^5$
• $0\leq$ nums[i] $\leq 10^4$

Examples#

Try it yourself#

Implement your solution in the following playground.

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack Dynamic programming pattern.

Naive approach#

The naive approach is to find the possible combinations from the set, which makes up our target_sum. We know that we have to trace down all subsets. Therefore, we have to evaluate every element of the set.

For example, we have the following set of positive values given along with a target_sum of $13$:

• set: $\{$ $3, 5, 8, 10$ $\}$

The subsets whose sum will be equal to the target_sum are:

• $\{$ $5, 8$ $\}$
• $\{$ $10, 3$ $\}$

We cannot do $5 + 5 + 3 = 13$ because we can consider each element only once.

So, we need a recursive solution to make all these calculations, as shown above. In other words, we will divide our problem into smaller subproblems, starting from the start of the nums list and for each element, we will do the following steps:

• Check for the following base cases:

  • If the target_sum is 0, it means that we can reach the sum of $0$ without including any element in our subset resulting in an empty subset, so we return 1 to include an empty subset.

  • If we have traversed all of our elements then we cannot proceed further to calculate the required sum. So we return 0.

• Consider the current element for the required sum.

  • If it contributes to making up the target_sum, we subtract the target_sum from the current number and proceed on to the next number with the new target sum of target_sum – nums[current_index].

• Do not consider the contribution of the current element for the target_sum and move on to consider the rest of the numbers.

Let’s try to implement the algorithm as discussed above:

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is $O(2^n)$, where $n$ is the total number of elements. This is because we have two possible choices every time, either to include the item or not.

Space complexity#

As the maximum depth of the recursive call tree is $n$, and each call stores its data on the stack, the space complexity of this approach is $O(n)$.

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in a table.

As we have to check each possible combination of all elements present in nums, we can store computed values and use them later whenever we need. For this, we will use a 2-D array to store the computed results at each step. Whenever we encounter a subproblem whose value is already calculated, we will simply fetch our already computed result instead of doing all the calculations again. This fetching takes place in $O(1)$ time.

The 2-D array will be of size $input \space set \space size \times (target+1)$ and initialized with $-1$ to indicate that these subproblems are yet to be solved. The rows correspond to each element in the input array and the columns correspond to the remaining sums from $0$ to the target sum. So, for a given number and the remaining sum, we’ll do the following in the helper function:

• Check the base cases as done in the naive approach.

• If you look at the code shown below, you will see that we are checking if the count of subsets for a given element and the remaining sum has already been evaluated or not.

  • If it hasn’t already been evaluated, evaluate it as done in the naive approach and store the result in the 2-D array at lookup_table[current_index][required_sum]. The current_index specifies the index of the current element in the nums array.

  • If it has already been evaluated, fetch the computed result from lookup_table[current_index][required_sum].

Let’s implement this algorithm:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we avoided redundant calculations by storing all the intermediate results in a 2-D array, the time complexity of this approach is reduced to $O(n * s)$, where $n$ is the number of elements and $s$ is the target sum.

Space complexity#

The space complexity of the top-down solution is $O(n * s)$, corresponding to the size of the 2-D array used to store intermediate values.

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. A 2-D array of size $s \times (t+1)$, where $s$ is the input set size and $t$ is the target sum, which is used to store the results of subproblems. All the cells in the table are initialized to $0$. In each iteration, we consider a number from the input set and check if that number can be included in our subset to reach the remaining sum. If you look at the code shown below, you will see the following steps to calculate the count of the subset sum:

• Check the base case for the first number:

  • If the first number in the input array is $0$, we update the cell at lookup[0][0] to $2$ because the empty set and the set ${0}$ will both contribute to the zero sum.

  • If the first number is not $0$, we update the cell at lookup[0][0] to $1$ because only the empty set will contribute to the zero sum. Also, if the number is less than the $target$, it’ll contribute towards the $target$, so update the cell at lookup[0][nums[0]] to $1$.

• We iterate the input array starting from the $1st$ index, and for each of the numbers, we perform two steps for each required_sum from $0$ to $target$:

  • Exclude the number. Get the count of all the subsets before the given number by fetching the value from lookup[current-1][required_sum].

  • Include the number if its value is not more than the required_sum. Get the count of all the subsets for the remaining target of required_sum - nums[current] by fetching it from lookup[current-1][required_sum - nums[current]].

  • Add the counts and store it in lookup[current][required_sum].

• After all the calculations, lookup[nums_len - 1][target_sum] has the count of all the subsets having the sum equal to the target_sum.

Let’s see the illustration below to understand the algorithm.

Note: The cells in yellow are the current indexes being processed. The cells in purple are counts fetched from the previous iteration. The ind variable in the slides is the same as the current variable used in the explanation/code.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of this approach is reduced to $O(n * s)$, where $n$ is the number of elements and $s$ is the target sum.

Space complexity#

We need $O(n * s)$ space in memory to store the intermediate values.